package com.dy.分类.栈队列堆.数据流中的中位数;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {
    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        medianFinder.findMedian();
    }
}
//一个大顶堆，一个小顶堆，大顶堆存前 n/2 个数，
class MedianFinder {
    PriorityQueue<Integer> smallHeap;
    PriorityQueue<Integer> bigHeap;
    /** initialize your data structure here. */
    public MedianFinder() {
        smallHeap = new PriorityQueue<>();
        bigHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
    }

    /**如果大顶堆和小顶堆长度相等：
     *      1、如果 数比大顶堆大，则加入小顶堆
     *      2、如果 数比大顶堆小，则加入大顶堆
     * 如果大顶堆长度大于小顶堆：
     *      1、如果数比大顶堆大，加入小顶堆
     *      2、如果数比大顶堆小，将大顶堆堆顶加入小顶堆，大顶堆加入新数
     * 如果大顶堆长度小鱼小顶堆：
     *
     */
    public void addNum(int num) {
        if(bigHeap.isEmpty()){
            bigHeap.offer(num);
        }
        //长度相等时
        else if(bigHeap.size()==smallHeap.size()){
            if(num>bigHeap.peek()){
                smallHeap.offer(num);
            }
            else{
                bigHeap.offer(num);
            }
        }
        //如果大顶堆长度大于小顶堆
        else if(bigHeap.size()>smallHeap.size()){
            if(num>=bigHeap.peek()){
                smallHeap.offer(num);
            }
            else{
                int tmp = bigHeap.poll();
                smallHeap.offer(tmp);
                bigHeap.offer(num);
            }
        }
        //小顶堆长度长
        else{
            if(num<=smallHeap.peek()){
                bigHeap.offer(num);
            }else{
                int tmp  = smallHeap.poll() ;
                bigHeap.offer(tmp);
                smallHeap.offer(num);
            }
        }



    }

    public double findMedian() {
        if(bigHeap.size()==smallHeap.size()){
            return ((double)bigHeap.peek()+(double)smallHeap.peek())/2;
        }else if(bigHeap.size()> smallHeap.size()){
            return bigHeap.peek();
        }else return smallHeap.peek();
    }
}
